package Leetcode.链表;

import Leetcode.ListNode;

/**
 *https://leetcode-cn.com/problems/reverse-linked-list-ii/
 * 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
 * 说明:
 * 1 ≤ m ≤ n ≤ 链表长度。
 * 示例:
 * 输入: 1->2->3->4->5->NULL, m = 2, n = 4
 * 输出: 1->4->3->2->5->NUL
 */
public class L92_翻转链表II {
    /**
     * 这题特别点是，返回的话还是返回正常顺序
     * 跟之前完全翻转是完全不一样
     * 这个操作没啥特别的，就是细节要想明白比较难
     */
    public ListNode reverseBetween(ListNode head, int m, int n) {
        //m有可能会取第一，专门处理麻烦。 所以，申请个节点，好处理
        ListNode preHead = new ListNode(0);
        preHead.next = head;
        ListNode pre = preHead;
        //找到第m位置,从1开始，因为我们多加一个节点，最后找到 pre=1, cur=2
        for(int i=1; i<m; i++){
            pre = pre.next;
        }
        //上面的例子，这时候pre是2， h是当前头 是 3
        ListNode h = pre.next,right;//这里的h，相当于是m节点的前驱，一直保持不变
        for(int i=m; i<n; i++){//直接从m开始是因为上面已经定位到cur了
            right = h.next;//记下当前有指针的下个点，比如这里是3
            //下面的操作跟之前链表翻转不一样
            //1-->2-->3-->4-->5
            //1-->3-->2-->4-->5
            //1-->4-->3-->2-->5
            //下面几步必须要这个顺序
            //上面的操作，就是，h是2， right是3
            //将h2子节点，改为 right 3的子节点
            h.next = right.next;//3的下节点，指导自己节点的数，也就是4
            right.next = pre.next;//断开和下游关系，改为pre 1的下游

            //下面是比较单独的步骤
            pre.next = right;//pre一直是没变的，一直是1，这个要注意
        }

        return preHead.next;
    }

    public static void main(String[] args){

        ListNode head = new ListNode(1);
        ListNode l5 = new ListNode(5);
        ListNode l4 = new ListNode(4);
        l4.next = l5;
        ListNode l3 = new ListNode(3);
        l3.next = l4;
        ListNode l2 = new ListNode(2);
        l2.next = l3;
        head.next = l2;

        L92_翻转链表II l = new L92_翻转链表II();
        l.reverseBetween(head, 2,4);

    }

}
